/*
 * @Description: 无重复字符的最长子串
 * @FilePath: \算法\字符串\3.无重复字符的最长子串.js
 */ 
/*
 * @lc app=leetcode.cn id=3 lang=javascript
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
/*  滑动窗口 

    时间复杂度: O(n^2)
    空间复杂度: O(1)
*/
// var lengthOfLongestSubstring = function(s) {
//     let len = s.length;
//     let l = 0, r = -1;
//     let num = 0;

//     while(r < len) {
//         if(s.slice(l,r).indexOf(s[r]) < 0) {
//             num = Math.max(r-l+1, num);
//             r++;
//         } else {
//             l++;
//         }
//     }
//     console.log(num);

//     return num;
// };


/*  滑动窗口+备忘录 

    1. 定义一个l，r。在[r...l]中判断是否存在重复的元素
    2. 如果重复，找到重复的位置，将r指向重复的位置+1
    3. 否则r++
*/
var lengthOfLongestSubstring = function(s) {
    let len = s.length,
        l = 0, 
        r = 0,
        record = {},    // 备忘录，记录每个元素出现的次数
        res = 0;
    // if(len < 2) return len;
    while(r < len) {
        if(!record[s[r]]) {
            record[s[r]] = r;
            res = Math.max(res, r-l+1);
            r++;
            console.log(record);
        } else {
            delete record[s[l++]];
            console.log(l);
        }
    }
    console.log(l, r);

    return res;
};
let res = lengthOfLongestSubstring("aabca");
console.log(res);
// @lc code=end
